package com.sheng.leetcode.year2022.swordfingeroffer.day31;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/09/29
 *<p>
 * 剑指 Offer 44. 数字序列中某一位的数字<p>
 *<p>
 * 数字以0123456789101112131415…的格式序列化到一个字符序列中。<p>
 * 在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。<p>
 * 请写一个函数，求任意第n位对应的数字。<p>
 *<p>
 * 示例 1：<p>
 * 输入：n = 3<p>
 * 输出：3<p>
 *<p>
 * 示例 2：<p>
 * 输入：n = 11<p>
 * 输出：0<p>
 *<p>
 * 限制：<p>
 * 0 <= n <2^31<p>
 * 注意：本题与主站 400 题相同：<a href="https://leetcode-cn.com/problems/nth-digit/">...</a><p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0044 {

    @Test
    public void test01() {
        int n = 3;
//        int n = 11;
        System.out.println(new Solution44().findNthDigit(n));
    }
}
class Solution44 {
    public int findNthDigit(int n) {
        if (n < 0) {
            return -1;
        }
        int place = 1;  // 1 表示个位，2 表示 十位...
        while (true) {
            // 获取n位数字连起来对应的数字的个数
            int amount = getAmountOfPlace(place);
            // 乘以位数，获取连起来的长度
            int totalAmount = amount * place;
            // 小余时
            if (n < totalAmount) {
                return getDigitAtIndex(n, place);
            }
            // 减去对应的长度
            n -= totalAmount;
            // 位数加1
            place++;
        }
    }

    /**
     * place 位数的数字组成的字符串长度
     * 10, 90, 900, ...
     */
    private int getAmountOfPlace(int place) {
        if (place == 1) {
            // 0~9
            return 10;
        }
        // 其他长度为90,900...，即9 * 10 ^ (place - 1)
        return (int) Math.pow(10, place - 1) * 9;
    }

    /**
     * place 位数的起始数字
     * 0, 10, 100, ...
     */
    private int getBeginNumberOfPlace(int place) {
        if (place == 1) {
            return 0;
        }
        return (int) Math.pow(10, place - 1);
    }

    /**
     * 在 place 位数组成的字符串中，第 index 个数
     */
    private int getDigitAtIndex(int index, int place) {
        int beginNumber = getBeginNumberOfPlace(place);
        int shiftNumber = index / place;
        String number = (beginNumber + shiftNumber) + "";
        int count = index % place;
        return number.charAt(count) - '0';
    }
}
